Міністерство освіти та науки України Національний університет „Львівська політехніка” кафедра ЕОМ Лабораторна робота №2 з курсу: „Алгоритми і засоби цифрової обробки сигналів” Тема: „Сортування даних, пошук екстремальних значень. Аналіз характеристик алгоритмів ЦОСЗ” Львів – 2003 р. Мета роботи: Вивчення алгоритмів швидкого сортування даних згідно з заданим законом, пошуку екстремальних значень даних. Дослідження часової і об’ємної (за об’ємом па’мяті) складності алгоритмів сортування і області їх застосування. № Завдання  33 Вставити нові елементи у відсортовану за неспаданням послідовність Integer: а) довжина послідовності - 1024, 32788 елементів; б) послідовність генерувати функцією Random; в) час роботи програми вимірювати функцією GetTime;   Теоретичні відомості Складовою частиною більшості алгоритмів ЦОСЗ є процедури сортування, перестановки даних. До них відносяться: а) сортування елементів по зростанню/спаданню; б) перестановка елементів масиву по закону двійкової інверсії; в) розділення масиву на парні і непарні елементи. Характеристики виконання цих процедур впливають на ефективність алгоритмів ЦОСЗ в целому. Оскільки для розв’язання задач сортування і перестановки даних існують алгоритми різного типу, необхідно, в залежності від вихідних даних і умов задачі вибрати найефективніші за комплексним критерієм "швидкодія – об’єм використаної пам’яті". Алгоритми сортування даних. Серед відомих алгоритмів сортування даних по зростанню/спаданню значень елементів виділяють: а) сортування "вичерпуванням"; б) сортування методом "бульбашки"; в) сортування злиттям. Оптимальне застосування кожного з цих алгоритмів залежить від значень елементів даних, які необхідно відсортувати і умов виконання задачі. Сортування "вичерпуванням". Алгоритм з обчислювальною складністю N; можна застосовувати тільки до даних з малим динамічним діапазоном. Для побудови алгоритму необхідно створити масив вказівників розміром, який рівний динамічному діапазону вхідних даних. Hаприклад, для елементів даних розміром один байт необхідно створити масив вказівників на 256 елементів. Опис алгоритму: 1) вибрати біжучий елемент (зі значеням L) з вхідного масиву даних; 2) проаналізувати значення елемента з адресою L в масиві вказівників; 3) якщо значення вказівника L є нульовим, то записати туди зсилку на біжучий елемент вхідного масиву, а в біжучий елемент записати 0; 4) якщо значення ненульове, то аналізувати ланцюг зсилок поки не буде знайденне «0» значення; 5) в комірку з знайденим «0» записати зсилку на біжучий елемент, а в біжучу комірку записати «0»; 6) перейти на обробку наступного елемента. В результаті роботи алгоритму створюються два масиви зсилок: первинний і вторинний (створений з вхідного масиву). Вторинний масив необхідний при необхідності відновлення початкової послідовності При відсутності такої необхідності алгоритм спрощується. Добавлення нових елементів до відсортованих зводиться до прослідковування ланцюжка зсилок або додавання «1» до значення елемента в первинному масиві (в спрощеному варіанті). Сортування методом "бульбашки". Один з найпростіших для реалізації алгоритмів, обчислювальна складність якого N2 . Він може бути застосований при сортуванні даних довільного динамічного діапазону. Опис алгоритму. 1) вибрати біжучий елемент; 2) порівняти його з останнім відсортованим елементом; 3) зупинитися, якщо результат порівняння відповідає умові сортування і перейти на п.1); 4) якщо результат порівняння не відповідає умові сортування, поміняти елементи місцями і перейти на п.2. По даному алгоритму приходиться рухатися по відсортованому масиві вверх, до пір, поки не буде знайдене місце для біжучого елемента. Тому однозначно оцінити час роботи неможливо, в гіршому випадку він пропорційний N2. Сортування злиттям. Алгоритм сортування злиттям має структуру швидких алгоритмів і зводиться до розбиття вхідного масиву розміром N на два підмасиви розміром N/2. Дроблення продовжується до тих пір, поки не залишаться два елементи (вхідн...